package com.zwj.interview.二分查找;

/**
 * 二分查找
 */

public class 二分查找模板 {

    //标准的二分查找方法
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            //为了防止溢出，我们不用(left + right) / 2，使用下面这个写法，两者意思一样
            int mid = left+(right-left)/2;
            if (nums[mid] == target) {
                return nums[mid];
            }
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

   //寻找目标值的左侧边界是否还有跟目标值一样的值
    public int left_bound(int[] nums,int target){
        int left = 0;
        int right = nums.length - 1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(nums[mid]<target){
                left=mid+1;
            }else if(nums[mid]>target){
                right=mid-1;
                //中间值等于目标值，那么缩小范围
            }else if(nums[mid]==target){
                right=mid-1;
            }
        }
        //left走完整个数组，都没有target，则返回-1
        if(left>=nums.length || nums[left]!=target){
            return -1;
        }
        return left;
    }

    //寻找目标值的右侧边界
    public int right_bound(int[] nums,int target){
        int left = 0;
        int right = nums.length - 1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(nums[mid]<target){
                left=mid+1;
            }else if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]==target){
                left=mid+1;
            }
        }
        if(right<0 || nums[right]!=target){
            return -1;
        }
        return right;
    }
}
